1. Field of the Invention
The present invention relates in general to computer-aided design tools for generating IC layouts and in particular to a method for eliminating cell overlap and routing congestion in an IC layout.
2. Description of Related Art
FIG. 1 illustrates a typical integrated circuit (IC) design process flow. An IC designer usually begins the IC design process by producing a register transfer language (RTL) xe2x80x9cnetlistxe2x80x9d 10, a file describing the IC circuit as a set of nets (signal paths) interconnecting terminals of the various circuit devices (xe2x80x9ccellsxe2x80x9d) to be included in the IC. In a high level RTL netlist cells may be described in terms of the logic they carry out, using Boolean expressions to define logical relationships between device input and output signals. After employing circuit simulation and verification tools 11 to check the logic of the IC described by RTL level netlist 10, the designer uses a synthesis tool 12 to convert RTL level netlist 10 into a xe2x80x9cgate levelxe2x80x9d netlist 14 describing each cell by referring to an entry for that cell in a cell library 13, which includes an entry for each cell that may be incorporated into an IC design. Cells described by cell library 13 may range from very small devices such as individual transistors, to small components such as logic gate formed by several transistors, up to very large components such as computer processors and memories.
The cell library entry for each cell contains a model of the time-dependent behavior of the cell that can be used to represent the cell when a gate level netlist 14 incorporating the cell into an IC design is subjected to simulation and verification 11. A simulation based on gate level netlist 14 more accurately predicts the behavior of the IC than a simulation based on RTL level netlist 10. However since the gate level netlist 14 does not model the networks interconnecting the cells, the simulation and verification results at this stage of the design do not take into account signal path delays in the nets.
After verifying the behavior of the circuit described by gate level netlist 14, the circuit designer employs computer-aided placement and routing (PandR) tools 16 to convert gate level netlist 14 into an IC layout describing how each cell is to be formed and positioned within a semiconductor substrate and describing how the nets interconnecting the cells are to be routed. The cell library entry for each cell also contains a detailed description of the cell""s layout telling the PandR tools 16 how to lay out that cell. The PandR tools determine where to place each cell and how to orient each cell in the substrate and also determine how to route the nets that interconnect the cells.
As PandR tools 16 create an IC layout, a xe2x80x9cnetlist updaterxe2x80x9d 20 updates the gate level netlist 14 to produce a xe2x80x9clayout levelxe2x80x9d netlist 22 not only models the cells forming the IC but also models the signal path delays within the nets interconnecting the cells. After PandR tools 16 have generated layout 18, the designer may again use simulation and verification tools 11 to verify the behavior of the circuit based on the more accurate layout level netlist 22 before sending the completed IC layout 18 to an IC manufacturer.
FIG. 2 illustrates a typical example of an iterative placement and routing process carried out at step 16 of FIG. 1. The designer may initially create a floor plan (step 24) for the layout when particular areas of the semiconductor substrate are to be reserved for particular cells. A PandR tool then develops a placement plan (step 26) indicating where each cell referenced by gate level netlist 14 is to be placed and how it is to be oriented within a semiconductor substrate in a manner consistent with the floor plan. Thereafter the PandR tool develops a routing plan (step 28) describing the paths followed by the nets interconnecting cell terminals. The placement and routing steps 26 and 28 are iterative in that when the PandR tool is unable to develop a routing plan at step 28 providing a suitable route for every net of the design, it returns to step 26 to reposition the cells and then attempts to develop a suitable routing plan for the altered placement plan at step 28.
Within most digital ICs, signals pass between blocks of logic through clocked devices such as registers and flip-flops so that the clock signals clocking those devices can synchronize the timing with which the logic blocks pass signals to one another. The logic blocks are therefore subject to timing constraints in that they must be able to process their input signals to produce their output signals within the period between clock signal edges. The time required for a logic block to process its input signals is a function of the processing speed of each cell within the logic block involved in the signal processing, and is also a function of the signal path delays through the various nets interconnecting those cells. Although the placement and routing tools may find space in the layout for all cells and for all of the nets interconnecting them at steps 26 and 28, the path delays through some of the logic blocks may fail to meet timing constraints.
Thus after the PandR tools have established placement and routing plans at steps 26 and 28, it is necessary to verify that all logic blocks meet their timing constraints. To do so, an xe2x80x9cRC extraction toolxe2x80x9d initially processes routing plan (step 30) to determine resistances and capacitances of the various sections of nets described by the routing plan and passes that information to a timing analysis tool. Since the path delay through a net is a function of its resistance and capacitance (path inductance is usually neglected) the timing analysis tool (at step 32) is able to compute path delays through the various nets based on the resistance and capacitance information provided by the RC extraction tool. The timing analysis tool also consults the cell library to determine the path delay through each cell of interest.
Based on the information provided by the timing analysis tool, the placement and routing plans are subjected to an xe2x80x9cin place optimizationxe2x80x9d process (step 34) in which the path delays through the various logic blocks are analyzed to determine whether they meet their timing constraints. When a logic block fails to meet a timing constraint, the placement plan can be incrementally modified (step 35) by inserting buffers in signal paths to reduce path delays or by moving cells of the logic block closer together or resizing cells to reduce path delays between the cells. The routing plan is then altered (step 28) as necessary to accommodate the altered placement plan. The RC extraction process (step 30) and the timing analysis process (step 32) may also be repeated. The process iterates through steps 28, 30, 32, 34 and 35 until placement and routing plans satisfying all timing constraints are established.
The layout process may also include a step of checking the layout for various signal integrity problems (step 36) including, for example, static timing analysis and cross-talk analysis, and may iteratively modify the placement and routing plans at step 35 to resolve these problems.
A clock tree synthesis tool may also be employed to design one or more clock trees (step 37) for the IC. A clock tree is a network of buffers for distributing a clock signal to the various registers, flip-flops and other clocked circuit devices. The clock tree design specifies a position for each buffer forming the clock tree and the routing paths interconnecting the buffers that will ensure that each clock signal edge arrives all clocked devices at substantially the same time. After the clock tree has been designed, the placement and routing plans are modified (steps 35 and 28) as necessary to incorporate the buffers and nets forming the clock tree into the layout.
A power analysis step 39 may also be carried out in which the layout is analyzed to determine whether power loads are adequately distributed throughout the power distribution network that delivers power to all cells.
When the layout process is unable to produce a layout based on gate level netlist 14 that satisfies all constraints, it may be necessary at step 40 to restructure the logic of the IC design (i.e. to modify gate level netlist 14) and then repeat the entire placement and routing process.
As may be seen from the above discussion, the placement and routing plans may be incrementally modified many times at steps 35 and 28 following in place optimization, clock tree synthesis, and power analysis steps in which cells may be added to the design. A placement plan can also be modified when there is a change to an IC design, for example when the designer wants to make a global change to a particular kind of cell having instances appearing in several parts of the layout or when the designer wants to incorporate additional cells into the layout, for example in response to an engineering change order.
Whenever the cells are to be added to a layout or increased in size, a cell overlap problem can arise. For example clock tree synthesis step 37 generates a clock tree design specifying that buffer cells are to be added at particular points within the layout, and when the PandR tool modifies the layout at step 35 to place the buffer cells at the specified points, it may have to relocate cells already residing at those points. This may not significantly alter the layout when vacant positions are available near the points of interest, but when areas of the layout surrounding the points of interest are so densely packed with cells that nearby vacant positions are not available, it may be necessary for the PandR tool to reposition a large number of cells in order to accommodate the new buffer cells. Similar cell overlap problems can arise when global replacements affect the size or aspect ratio of various types of cells.
When we modify a layout that already satisfies various design criteria, the modification may cause the layout to violate the design criteria. For example, when clock tree synthesis step 37 occurs after in-place optimization step 34, the modifications to the layout needed to accommodate the clock tree can spoil the layout""s ability to meet design criteria that were satisfied during the in-place optimization step. Since the likelihood of such an unfortunate effect occurring as a result of a modification to a layout increases with the severity of the modification, it is helpful when repositioning cells to eliminate cell overlap to do so in a manner that minimizes the disturbance to the layout with respect to the number of cells that must be repositioned and the distance the cells are moved. Thus what is needed is a method that can help a PandR tool to determine how to reposition cells to eliminate cell overlap in a manner that substantially minimizes the disturbance to the layout.
As discussed above a conventional placement and routing tool initially creates a placement plan (step 26) specifying the position and orientation of each cell and then creates a routing plan (step 28) specifying the manner in which the nets interconnecting the cells are routed. During the process of creating the routing plan various areas of the layout can become too congested with nets to accommodate all of the nets that must pass through them. When that happens, the PandR tool must return to step 26, revise the placement plan by repositioning cells in a manner that eliminates routing congestion and then try again at step 28 to develop a suitable routing plan. What is needed is a method that can help the PandR tool to determine how to revise a placement plan with a routing congested layout so as to substantially increase the routability of the layout.
The invention relates to a method for determining how to reposition cells within an IC layout either to eliminate cell overlap or routing congestion.
In accordance with the invention, the layout is initially organized into an array of blocks, each having capacity to hold several cell units wherein a cell unit spans a unit of substrate area of standard dimensions. A separate equation is established for each block relating a sum of a set of flow variables to an xe2x80x9coverflow factorxe2x80x9d. Each flow variable of the equation for each block corresponds to a separate one of that block""s neighboring blocks, and represents an estimated number of cell units that are to be moved to or received from the corresponding neighboring block to eliminate overlapping cell placements or routing congestion within the block. The overflow factor for each block represents an estimated total number of cells the block must pass to its neighboring blocks or a maximum number of cells it may receive from its neighboring blocks in order to eliminate cell overlap or routing congestion in all blocks.
Although many solutions to the set of simultaneous equations are possible, the method preferably searches for and selects the solution that minimizes a sum of squares of the flow variable values of all equations. This particular solution to the set of equations provides flow variable values which, when subsequently used to guide cell relocation, substantially reduces the likelihood of cell overlap or routing congestion while substantially minimizing disturbance to the layout.
The layout is then modified by moving cells between neighboring blocks wherein the total number of cell units moved between each pair of neighboring blocks and the direction in which they are moved is guided by the flow variable values provided by the selected solution.